<?php 

/** 
 * 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
 */

/** 
 * 解法一
 * 由题意得，当数组排好序后，超过数组一 半的数必定是在中间的位置上
 * 可根据快速排序，求第K小的数的位置的思路，求K位于中间时的数的值，就是要求的值
 * @param [type] $array [description]
 */
function MoreThanHalfNum_Solution($array)
{
  	if (!is_array($array) || empty($array)) {
  		return null;
  	}
    $length = count($array);
  	$middle = intval($length>> 1);
  	$start = 0;
  	$end = $length - 1;
  	$index = Partition($array, $start, $end);
  	while ($index != $middle) {
  		if ($index > $middle) {
  			$end = $index - 1;
  			$index = Partition($array, $start, $end);
  		} else {
  			$start = $index + 1;
  			$index = Partition($array, $start, $end);
  		}
  	}
  	$result = $array[$index];
    

    $times = 0;
    for ($i = 0; $i < $length; $i++) {
    	if ($array[$i] == $result) {
    		$times++;
    	}
    }
    if ($times < $middle) {
    	return null;
    }
    return $result;
}

function Partition(&$array, $start, $end)
{   
	$temp = $array[$start];
	while ($start < $end) {
		while (($start < $end) && ($array[$end] >= $temp)) {
			$end--;
		}
		$array[$start] = $array[$end];
		while (($start < $end) && ($array[$start] <= $temp)) {
			$start++;
		}
		$array[$end] = $array[$start];
	}
	$array[$start] = $temp;
    return $start;
}

/** 

采用阵地攻守的思想：
第一个数字作为第一个士兵，守阵地；count = 1；
遇到相同元素，count++;
遇到不相同元素，即为敌人，同归于尽,count--；当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。
再加一次循环，记录这个士兵的个数看是否大于数组一般即可
 * @param [type] $array [description]
 */
function MoreThanHalfNum_Solution1($array)
{
	if (!is_array($array) || empty($array)) {
  		return null;
  	}

  	$result = $array[0];
  	$times = 1;
  	foreach ($array as $key => $value) {
  		if ($times == 0) {
  			$result = $value; // 最后还留在的，就是最后一次对result赋值的value
  			$times = 1;
  		}
  		if ($result == $value) {
  			$times ++;
  		} else {
  			$times --;
  		}
  	}



  	$counts = 0;
  	$middle = count($array) >> 1;
    for ($i = 0; $i < count($array); $i++) {
    	if ($array[$i] == $result) {
    		$counts++;
    	}
    }
    if ($counts < $middle) {
    	return null;
    }
    return $result;

}

$arr = [1,2,3,2,2,2,5,4,2];
var_dump(MoreThanHalfNum_Solution1($arr));